#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>
#include <time.h>
using namespace std;
class Solution
{
public:
    void quick_sort(vector<int> &nums, int left, int right)
    {
        if (left >= right)
            return;
        int random = rand() % (right - left + 1) + left;
        swap(nums[random], nums[left]);
        // cout << nums[left] << endl;
        int lend = left + 1, rhead = right;
        for (int i = left + 1; i <= rhead; ++i)
        {
            while (i <= rhead && nums[i] > nums[left])
                swap(nums[i], nums[rhead--]);
            if (nums[i] < nums[left])
                swap(nums[lend++], nums[i]);
        }
        swap(nums[lend - 1], nums[left]);
        // for(auto e: nums) cout << e << ' ';
        // cout << endl;
        // cout << lend << ' ' << right << endl;
        quick_sort(nums, left, lend - 1);
        quick_sort(nums, rhead + 1, right);
    }
    vector<int> sortArray(vector<int> &nums)
    {
        srand(time(NULL));
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};